package 算法基础模板.chapter_03;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * @author Summerday
 */
public class GraBFS {

    static int n;
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int m = sc.nextInt();
        Graph g = new Graph(n + 1);
        while(m -- > 0){
            int a = sc.nextInt(), b = sc.nextInt();
            g.add(a, b);
        }
        System.out.println(bfs(g, 1));
    }

    static int bfs(Graph g, int u){
        int[] d = new int[n + 1];
        Arrays.fill(d, -1 );
        Queue<Integer> q = new LinkedList<>();
        q.offer(u);
        d[u] = 0;
        while(!q.isEmpty()){
            int t = q.poll();
            for(int i = g.h[t]; i != -1; i = g.ne[i]){
                int j = g.e[i];
                if(d[j] != - 1) continue;
                d[j] = d[t] + 1;
                q.offer(j);
            }
        }
        return d[n];
    }
}
